/*******************************************
rbtree 五条性质
性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是NIL节点）。
性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 
性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
*******************************************/

#ifndef _RBTREE_H_
#define _RBTREE_H_

/**********************************
write by zhangliang <liangzhws@foxmail.com>
**********************************/

#ifndef NULL

#define NULL     0

#endif

#ifndef __BOOL
#define __BOOL

typedef int bool;

#define false    0
#define true     1

#define false    0
#define true     1

#endif


#ifndef _INIT_HEAD
#define _INIT_HEAD

#define init_head(type, head) init_head_##type(head)

#endif


#ifndef __ENTRY
#define __ENTRY

#define entry(ptr, type, member) (type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))

#endif

/***********************************************
rbtree model:
            ------
   head    | head |
            ------\
                   \
                    >   ------
                       | head |
                        ------
                       |father| --> NULL 
                        ------
                       | left | 
                        ------
                       |right |
                        ------
                       |color | black
                        ------
                       | key  |
                      / ------\
                     /         \
                ... <           > ...
**********************************************/

#define _RBTREE_S
#define _RBTREE_T

struct rbtree_head_s;

#define _RBTREE_COLOR_E
#define _RBTREE_COLOR_T

typedef enum rbtree_color_s {
	RED,
	BLACK
}rbtree_color_t;

#define _RBTREE_KEY_T

typedef long rbtree_key_t;

#ifndef INVAILD_KEY
#define INVAILD_KEY   -1
#endif

typedef struct rbtree_s {
	struct rbtree_head_s * head;
	struct rbtree_s *      father;
       	struct rbtree_s *      left;
	struct rbtree_s *      right;
	rbtree_color_t         color;	
	rbtree_key_t           key;
}rbtree_t;

#define NIL  (rbtree_t *)-1

#define _RBTREE_CMP_RESULT_E
#define _RBTREE_CMP_REULST_T

typedef enum rbtree_cmp_result_e {
	SMALL,
	EQUAL,
	BIG
}rbtree_cmp_result_t;

typedef rbtree_cmp_result_t (* cmp_op )(rbtree_key_t key1, rbtree_key_t key2);

inline rbtree_cmp_result_t rbtree_cmp_def(rbtree_key_t key1, rbtree_key_t key2);

#define RBTREE_OP_DEF  rbtree_cmp_def
#define RBTREE_OP_NULL (cmp_op)-1

#define _RBTREE_HEAD_S
#define _RBTREE_HEAD_S

typedef struct rbtree_head_s {
	rbtree_t * root;		
	cmp_op     op;
} rbtree_head_t;

#define init_head_rbtree_head_t(head) do {      \
		(head)->root = NIL;             \
		(head)->op = RBTREE_OP_DEF;     \
	}while (0)


/**
  @name:rbtree_is_empty
  @function: judge the head who is rbtree units manager is empty or not
  @param: #rbtree_head_t * head# head who is rbtree units manager
  @return: #bool# true is empty and false isn't empty
  @algorithm complexity: O(1)
*/
bool rbtree_is_empty(const rbtree_head_t * head);

/**
  @name:rbtree_empty
  @function: empty the head who is rbtree units maager
  @param: #rb_tree_head_t * head# head who is rbtree units manager
  @return: #void#
  @algorithm complexity: O(1)
*/
void rbtree_empty(rbtree_head_t * head);

/**
  @name:rbtree_is_root
  @function: judge the unit is root or not
  @param: #const rbtree_t * unit# rbtree unit
  @return: #bool# true is root and false isn't root
  @algorithm complexity: O(1)
*/
bool rbtree_is_root(const rbtree_t * unit);

/**
  @name:rbtree_set_cmp
  @function: change cmp function of rbtree
  @param:#rbtree_head_t * head# rbtree head who is rbtree unit manager
  @param:#const cmp_op op# new cmp function for compare rbtree unit key
  @return:#cmp_op# return old cmp function
  @algorithm complexity: O(1)
*/
cmp_op  rbtree_set_cmp(rbtree_head_t * head, const cmp_op op); 

/**
  @name:rbtree_set_key
  @function: set rbtree unit key value, any rbtree unit must be set
  @param: #rbtree_t * unit# rbtree unit
  @param: #rbtree_key_t key# rbtee unit's key
  @return: #void#
  @algorithm complexity: O(1)
*/
void rbtree_set_key(rbtree_t * unit, rbtree_key_t key);

/**
  @name:rbtree_get_key
  @functiton: get rbtree unit key value
  @param: #rbtree_t * unit# rbtree unit
  @return: #void#
  @algorithm complexity: O(1)
*/
rbtree_key_t rbtree_get_key(const rbtree_t * unit);

/**
  @name:rbtree_find
  @function: find rbtree unit by key
  @param: #rbtree_head_t * head# rbtree head whwo is rbtree unit manager
  @param: #rbtree_key_t key# rbtree key , it's unique in rbtree
  @return:#rbtree_t *# rbtree_t pointer point to rbtree unit, NULL is means find noting
  @algorithm complexity: O(log(n))
*/
rbtree_t * rbtree_find(rbtree_head_t * head, rbtree_key_t key);

/**
  @name:rbtree_insert
  @function: insert rbtree-unit into rbtree-head who is rbtree-unit manager
  @param: #rbtree_head_t * head# rbtree-head whoh is rbtree-unit manager
  @param: #rbtree_t * unit# rbtree-unit
  @return: #void#
  @algorithm complexity: O(log(n))
*/
void rbtree_insert(rbtree_head_t * head, rbtree_t * unit);

/**
  @name:rbtree_delete
  @function: delete rbtree-unit from rbtree-head who is rbtree-unit manager
  @param: #rbtree_t * unit# rbtree-unit
  @return: #void#
  @algorithm complexity: O(log(n))
*/
void rbtree_delete(rbtree_t * unit);

#endif /* _RBTREE_H_ */
